public class MyQueue {
    static class Node{
        public int val;
        public Node next;
        public Node(int val){
            this.val=val;
        }
    }
    public Node head;
    public Node last;
    public int usedSize;
    //入队，队尾入
    public void offer(int val){
        Node node=new Node(val);
        if (head==null){
            head=node;
            last=node;
        }else {
            //head不为null
            last.next=node;
            last=node;
        }
        usedSize++;
    }
    //出队，头删
    public int poll(){
        if (empty()){
            return -1;//抛异常,无头节点，无法删除
        }
        int ret=head.val;
        head=head.next;
        if (head==null){//如果只有一个节点，last也置空
            last=null;
        }
        usedSize--;
        return ret;
    }
    public boolean empty(){
        return usedSize==0;
    }
    public int peek(){
        if (empty()){
            return -1;//队列为空,无法返回元素
        }
        return head.val;
    }
    //循环队列，数组方式
    //判断是满还是空，有usedSize和牺牲一个空间

}
//设计循环队列
class MyCircularQueue {
    private int[] elem;
    private int rear;//尾
    private  int front;//头

    public MyCircularQueue(int k) {
        this.elem=new int[k+1];
    }

    public boolean enQueue(int value) {
        if (isFull()){
            //队列为空
            return false;
        }
        //队列不为空
        elem[rear]=value;
        rear=(rear+1)% elem.length;//rear跳到下一个,构成循环队列
        return true;
    }
    //出队列

    public boolean deQueue() {
        if (isEmpty()){//队列无元素
            return false;
        }
        //队列不为空
        front=(front+1)% elem.length;
        return true;

    }
    //获取头元素

    public int Front() {
        if (isEmpty()){//队列无元素
            return -1;
        }
        return elem[front];
    }
    //获取队尾元素

    public int Rear() {
        if (isEmpty()){//队列无元素
            return -1;
        }
        int index=(rear==0)? elem.length-1 : rear-1;
        return elem[index];
    }

    public boolean isEmpty() {
        return front==rear;
    }

    public boolean isFull() {
        if ((rear+1)%elem.length==front){
            //如果rear的后一个为front，则该rear位置不放元素，列为满的状态
            return true;
        }
        return false;
    }
}